The present invention, which relates generally to a search method for graphical data having one or more dimensions, is particularly suitable for searching through one or more frames of image data for the presence of one or more relevant objects therein that exhibit certain attributes. The term "graphical data", as used herein, means data that defines one or more characteristics of each of a matrix of points in a space of a given number of one or more dimensions (e.g., data represented in bit-map form or `pixel arrays`). The present invention is not directed to a search method for data originally represented in a coded form (e.g., data represented in ASCII code form).
A task in computer vision is to rapidly search for relevant objects within a scene. For such tasks as surveillance, object recognition and navigation, these relevant objects may be objects or events of interest. For such tasks as stereo depth and motion tracking, these relevant objects may be distinctive patterns matched between views represented by distinct image frames. For such tasks as reading textual material in graphical form (e.g., optical character reading or the like), these relevant objects may be individual characters, individual words or individual word groups (e.g., particular phrases, sentences, etc.).
Such tasks usually require substantial computation, and often must be accomplished in real time, in response to ongoing events. The problem, therefore, is to provide a search computation procedure which is fast (i.e., least expected search time) and efficient (i.e., least expected computation cost). An exhaustive search, accomplished by a serial approach, that compares a known relevant object at every sample position, is both slow and inefficient. Accomplishing the search by a parallel approach, which uses arrays of many processing elements to perform the comparisons at many image positions at the same time, is fast but is still inefficient because the same total computation is performed as in the sequential search technique.
The best approach is a guided approach, which employs information gained during earlier steps of the search procedure to selectively direct later steps of the search procedure to only those image regions most likely to contain the relevant objects. In this regard, the prior art has developed search procedures in which a coarse-resolution step of a relatively large image region is followed by a fine-resolution step which is limited to only those one or more sub-regions thereof which have been found likely by the coarse-resolution step to contain the relevant object. A good example of such a coarse-fine guided approach is disclosed in U.S. Pat. No. 4,692,806, issued to Anderson et al. on Sept. 8, 1987.
Reference is also made to my U.S. Pat. No, 5,063,603, filed Nov. 6, 1989 and assigned to the same assignee as the present application. This patent, incorporated herein by reference, discloses a dynamic image-processing method for general object recognition. For illustrative purposes, as an example, this reference application specifically discloses viewing objects in a room with a color television camera to obtain a television motion picture thereof in real time, and then dynamically analyzing the image data of each of a series of successive frames of this television motion picture for the purpose of recognizing any of a group of known individual persons in the television motion picture if that known individual person is present in the room. The disclosed illustrative example of this dynamic image-processing method makes use of (1) initially stored attributes, including templates of the facial characteristics of each of the group of known individual persons (2) the attribute that the facial color (e.g., fleshtone) of all of the persons of the group is known, (3) the attribute that a person is a movable object, and (4) additional stored attributes dynamically derived by the image-processing method during earlier-occurring frames of the series which are used to aid the analysis during the current frame of the series. This permits a number of recognition attributes sufficient to identify a known individual person to be built up from the total number of different attributes of the known individual person contained in an entire series of frames, although the number of different attributes of the known individual person contained in any single frame of the series is insufficient to identify a known individual person. This disclosed illustrative example of the reference application's dynamic image-processing method employs such techniques as pattern matching, fleshtone color detection and moving-object detection in a coarse-to-fine guided approach to achieve the desired object recognition of each known individual person of the group who happens to be in the television motion picture.
The coarse-to-fine guided approach disclosed in the aforesaid Anderson et al patent may be utilized repetitively in an image-processing method that extracts the location, in each successive current frame of a series of television frames, of only those pixels (if any) which define the same specified single attribute (which consists of the same single detected predetermined feature of interest) in each successive current frame only if those pixels exhibit an absolute-value level at least equal to a threshold. This single predetermined feature of interest may comprise any given criterion (such as pattern shape, moving object, etc.), or a particular combination of a plurality of such given criteria.